Atcoder abc167 题解

A~C太水了 不提

D：
大意：
给定N个节点，每个点都连向一个节点（可以是自己）。现在要从1号节点出发，问走了K步之后，到达的节点编号是几

分析：
K的数据范围特别大，很显然图中是一定存在一个环的，因此答案肯定跟循环节有关。
因此考虑以下三种情况：
① 1号节点自己是个自环，答案为1
② 1号节点走了几步之后，进入了一个环
③ 1号节点本身就在一个环内
很显然，这个题具体来说要找循环节的话，由于每个点有且仅有一条边，因此对于一个从1号点开始的路径，一旦有一个点往回走了（出现了一个之前出现的点），则必然是一个环路；同时，整个1开始的环路，一定只有这一个环，不可能再有多的了，因为只能连一条边，如果从回来的那个点再往前走出现一个环就连接了两条边，与题目矛盾。于是写一个dfs往下搜索就可以了，只要出现一个之前出现的点，则必然是找到了环路。不过这里就有一点点分歧了，对与②情况，是先走几步再进入环，而对于③来说则是1本身就在环路内。
对于②来说，首先做一个from数组，表示从1开始到循环节的第一个节点的路径。后面的就是环路的路径数组cir。答案比较好推，看代码即可

代码：https://atcoder.jp/contests/abc167/submissions/13077829

E：
大意：
一行内有n个格子，有M个颜色可以画到格子上。问至多有K对相同颜色的格子的方案数。
（n,M <= 2e5）

分析：
一看nm都是2e5，考虑dp的话得N2的递推了，好像不大可做。
考虑使用推组合数学：
既然要问的是K对格子，而提供的是一行n个格子，肯定要先转换一下，它组成的就是n-1对相邻的格子（做这个变换的原因就是考虑的元素是对数），对于一个∈[0,K]的$i$来说，相当于是在$n-1$对相邻的格子里选出i对来染成同样的颜色，这个颜色一共有$M$种选择方式，而剩余的$n - i - 1$块里每个块都有$M - 1$种选择，乘法原理然后一把乘起来就完事了。
res = $\sum\limits_{i=0}^km*C^i_{n-1}*(m-1)^{(n-i-1)}$

代码：https://atcoder.jp/contests/abc167/submissions/13108101

F：
大意：
有n个括号序列，问能不能通过某种方式把所有的序列拼起来组成一个合法的括号序列。
($n\leq10^6$)

分析：
这题目好像没什么条件，先来看一下什么时候无解：
第一个比较明显的条件是，括号序列的数量不匹配时肯定无解，把左括号看成1，右括号看成-1，则整个序列的和记作q的话，若最终拼出来的序列q不等于0，则不管怎么拼都是不合法的。
第二个条件是，把某一个序列从左到右看的话，存在一个右括号，它往左的左括号数量不够给他匹配了，则一定无解，因为一个在左边的右括号肯定不能被右边的左括号匹配了，到它如果不够数量就一定死了。于是可以找一下整个序列的前缀和最小值p，对于最终拼凑的结果序列，满足最小的p>=0即可。
现在来考虑，怎么样拼凑出一个合法的序列，或者说已知题目所给序列的p和q值，怎么知道能不能构造出一个合法的序列出来。很显然，当两个序列拼在一起时，他们的总和肯定是不变的，可以直接加和，但是他们俩的p值不同，p值是变化的，当插入一个新的序列的时候，整个序列的p最小值就会变成这个新加入的序列的p和前面的总和，因此对于一个新加入的序列$i$来说，假设它前面的所有序列和是sum的话，那么sum+$p_i$必须是>=0的。同时对于当前的这个序列和它后面的一个序列来说，他们俩的相对顺序不影响除他们俩之外的序列，于是考虑排序：对于某一对$i$<$j$来说，使得$i$在$j$前面的条件有两个部分：
一是满足$i$是合法的必须条件：
(记sum为i前面的所有q和，即sum = $\sum\limits_{j=0}^{i-1}q_j$)
$\begin{cases}sum + q_i \geq 0\\sum + q_i + p_j \geq 0\end{cases}$
二是满足j不合法的条件，两者满足一个就可以
$sum + p_j < 0$ 或 $sum + p_i + q_j < 0$
解出条件是:
$\begin{cases}q_i > 0\\p_i > p_j\end{cases}$
或是
$\begin{cases}q_j < 0\\q_i - p_i \geq q_j - p_j\end{cases}$
//注意第二个条件式里其实不能直接推出第二个条件，但是由于$q_j$是个负数，因此在右边加上它不影响不等式的成立，使得形式可以用于排序)
到这里就基本明确了，可以维护两个vector<pair<int,int>>，把q大于0的按p从大到小的顺序排列，把q小于0的按q-p从大到小排列，然后顺次把所有和加上，并判断中途是否会出现不合法情况就可以判断是否存在一个合法方案了。

代码：https://atcoder.jp/contests/abc167/submissions/13137693